home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / ch_hash1.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  3.0 KB  |  131 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  ch_hash1.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_CH_HASHING1_H
  17. #define LEDA_CH_HASHING1_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // Hashing with Chaining
  21. //
  22. // S. Naeher  (1994)
  23. //
  24. //------------------------------------------------------------------------------
  25.  
  26. #include <LEDA/basic.h>
  27.  
  28.  
  29. //------------------------------------------------------------------------------
  30. // class ch_hash1_elem  
  31. //------------------------------------------------------------------------------
  32.  
  33. class ch_hash1_elem 
  34. {
  35.   friend class ch_hash1;
  36.  
  37.   ch_hash1_elem* succ;
  38.   GenPtr k;
  39.   GenPtr i;
  40.  
  41.  
  42.   public:
  43.  
  44.   ch_hash1_elem(GenPtr key, GenPtr inf, ch_hash1_elem* next = 0) 
  45.   { k = key; 
  46.     i = inf; 
  47.     succ = next;
  48.    }
  49.  
  50.   ch_hash1_elem() {}
  51.  
  52.   LEDA_MEMORY(ch_hash1_elem)
  53.  
  54. };
  55.  
  56. typedef ch_hash1_elem*  ch_hash1_item;
  57.  
  58.  
  59. //--------------------------------------------------------------------
  60. // class ch_hash1
  61. //--------------------------------------------------------------------
  62.  
  63. class ch_hash1 
  64. {
  65.  
  66.    static ch_hash1_elem STOP;
  67.  
  68.    ch_hash1_elem* table;
  69.  
  70.    int table_size;           
  71.    int table_size_1;           
  72.    int low_table;           
  73.    int high_table;           
  74.    int count;
  75.  
  76.  
  77.    virtual int hash_fct(GenPtr x)      const { return long(x); }
  78.    virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  79.    virtual void clear_key(GenPtr&)  const { }
  80.    virtual void clear_inf(GenPtr&)  const { }
  81.    virtual void copy_key(GenPtr&)   const { }
  82.    virtual void copy_inf(GenPtr&)   const { }
  83.    virtual void print_key(GenPtr)   const { }
  84.  
  85.    virtual int_type() const { return 0; }
  86.  
  87.    int  next_pow(int) const;
  88.    void init(int);
  89.    void rehash(int);
  90.    void destroy();
  91.    ch_hash1_item search(GenPtr,ch_hash1_item&) const;
  92.  
  93.    protected:
  94.  
  95.    ch_hash1_item item(GenPtr p) const { return ch_hash1_item(p) ; }
  96.  
  97.    public:
  98.  
  99.    ch_hash1_item lookup(GenPtr x) const;
  100.  
  101.    ch_hash1_item insert(GenPtr,GenPtr);
  102.  
  103.    ch_hash1_item first_item() const { return 0; }
  104.    ch_hash1_item next_item(ch_hash1_item) const { return 0; }
  105.  
  106.    void del(GenPtr);
  107.    void del_item(ch_hash1_item);
  108.  
  109.    bool member(GenPtr x)   const  { return ( lookup(x) ? true : false ); } 
  110.  
  111.    GenPtr  key(ch_hash1_item p)  const { return p->k; }
  112.    GenPtr  inf(ch_hash1_item p)  const { return p->i; }
  113.    GenPtr& info(ch_hash1_item p)       { return p->i; }
  114.  
  115.    void change_inf(ch_hash1_item, GenPtr);
  116.    bool empty() const     { return count ? false : true ; } 
  117.    int  size()  const     { return count; } 
  118.    int  tablesize() const { return table_size ; }
  119.    void clear()           { destroy(); init(table_size);}
  120.  
  121.    ch_hash1& operator=(const ch_hash1&);
  122.    ch_hash1(const ch_hash1&);
  123.  
  124.    ch_hash1(int ts = 1<<10) { init(ts); /* init(next_pow(ts)); */ }
  125.    virtual ~ch_hash1()     { destroy(); }
  126.  
  127. };
  128.  
  129.  
  130. #endif
  131.